Ví dụ Thuật_toán_Dinitz

Dưới đây là một ví dụ thực hiện thuật toán Dinitz. Trong đồ thị tầng G L {\displaystyle G_{L}} , nhãn đỏ của các đỉnh là các giá trị dist ⁡ ( v ) {\displaystyle \operatorname {dist} (v)} . Các đường màu xanh tạo thành một luồng ngăn chặn.

G {\displaystyle G} G f {\displaystyle G_{f}} G L {\displaystyle G_{L}}
1.

Luồng ngăn chặn bao gồm

  1. { s , 1 , 3 , t } {\displaystyle \{s,1,3,t\}} với 4 đơn vị luồng,
  2. { s , 1 , 4 , t } {\displaystyle \{s,1,4,t\}} với 6 đơn vị luồng, và
  3. { s , 2 , 4 , t } {\displaystyle \{s,2,4,t\}} với 4 đơn vị luồng.

Do đó luồng ngăn chặn có 14 đơn vị luồng và tổng giá trị luồng | f | {\displaystyle |f|} là 14. Ghi chú là mỗi đường tăng luồng có 3 cung.

2.

Luồng ngăn chặn bao gồm

  1. { s , 2 , 4 , 3 , t } {\displaystyle \{s,2,4,3,t\}} với 5 đơn vị luồng.

Do đó luồng ngăn chặn có 5 đơn vị luồng và tổng giá trị luồng | f | {\displaystyle |f|} là 14 + 5 = 19. Ghi chú là mỗi đường tăng luồng có 4 cung.

3.

Vì không thể đến được t {\displaystyle t} trong đồ thị G f {\displaystyle G_{f}} , thuật toán kết thúc và trả về kết quả 19. Ghi chú là trong mỗi luồng ngăn chặn, số cung của mỗi đường tăng luồng tăng lên ít nhất một 1.